/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package jobscheduling.algorithms.glowworm;

import java.util.Map;
import java.util.Random;
import java.util.TreeMap;
import java.util.logging.Level;
import java.util.logging.Logger;

import jobscheduling.algorithms.AbstractScheduler;
import jobscheduling.algorithms.ResultListener;

/**
 *
 * @author Dawid
 */
public class GlowwormScheduler_new extends AbstractScheduler{
    private static final Map<String, String> _params = new TreeMap<String, String>();
    private static final Map<String, String> _descs = new TreeMap<String, String>();
    
	private int machines; // ilosc
	private int tasks; // ilosc
	private int ilosc; /* swietlikow */
	private Firefly[] ffs; /* swietliki */
	private int best; /* indeks najlepszego swietlika */
	/* parametry */
	private int bestTime = Integer.MAX_VALUE; /* trzyma najlepszy czas dotychczas, pomocniczo */
	private double gamma = 0.011;
	private double beta0 = 10;
	private double alpha = 5;
	private double potega = 1;
	private int[][] endingTimes; // czasy od poczatku do zakonczenia zadania na danej maszynie
	// dostep: endingTimes[zadanie][maszyna] - zadania wg kolejnosci w permutacji, nie wg kolejnosci z data
	// uzywana tylko w swietlikach, ale lezy tutaj dla oszczednosci pamieci
	
    
    static {
        _params.put("gamma", "1,0");
        _params.put("alfa", "1,0");
        _params.put("beta0", "1,0");
        _params.put("Ilosc", "10");

        _descs.put("gamma", "Współczynnik absorpcji światła");
        _descs.put("alfa", "Stopień losowości");
        _descs.put("beta0", "Bazowa atrakcyjność");
        _descs.put("ilosc", "Ilość świetlików");
    }
    
    public GlowwormScheduler_new (int[][] jobList, ResultListener listener, 
                              Map<String, String> params){
        super(jobList, listener, params);
        machines = jobList[0].length;
		tasks = jobList.length;
		endingTimes = new int[tasks][machines];
		ilosc = Integer.parseInt(params.get("ilosc"));
		gamma = Integer.parseInt(params.get("gamma"));
		beta0 = Integer.parseInt(params.get("beta0"));
		alpha = Integer.parseInt(params.get("alpha"));
		ffs = new Firefly[ilosc];
		for (int i = 0; i < ilosc; i++)
			ffs[i] = new Firefly(); /* po konstrukcji maja
										juz wylosowana permutacje
										startowa */
		
		findBest(); /* znajdz najlepszego w poczatkowej konfiguracji */

    }
    
    public static Map<String, String> getParamsPresets() {
        return _params;
    }

    public static Map<String, String> getParamsDescs() {
        return _descs;
    }
    

	/* Klasa swietlika */
	public class Firefly
	{
		private int[] permutation; /* aktualna permutacja */
		private double[][] probabs; /* prawdopodobienstwa przejsc */
		private boolean[] occupied; /* pomocnicza przy losowaniu
		 							i uaktualnianiu permutacji */
		private Random r = new Random();
		private int time; /* makespan dla permutacji tego swietlika - 
		 				czyli to, co minimalizujemy */
		private double[][] yi; /* tabelka polozen dla tego swietlika */
		private double[][] yj; /* polozenia dla swietlika, w ktorego stroe
								trza isc */
		
		public Firefly() {
			/* init */
			permutation = new int[tasks];
			probabs = new double[tasks][tasks];
			int num;
			occupied = new boolean[tasks];
			
			/* wszystko na false - wskazuje, czy dane liczby 
			 * juz wykorzystane sa w permutacji
			 */
			for (int i = 0; i < tasks; i++)
				occupied[i] = false;
			/* losowanie permutacji poczatkowej */
			for (int i = 0; i < tasks; i++) {
				do { /* szukaj jeszcze nie uzytej liczby */
					num = r.nextInt(tasks);
				} while (occupied[num]);
				occupied[num] = true; /* zajmij ja */
				permutation[i] = num; /* dopisz do perm. */
			}
			/* oblicz spantime poczatkowej permutacji */
			updateMakespanTime();
			/* init c.d. */
			yi = new double[tasks][tasks];
			yj = new double[tasks][tasks];
		}
		
		public int[] getPermutation() {
			return permutation;
		}
		
		public int getTIme() {
			return time;
		}
		
		private int getMakespanTime() {
			// wyzeruj czasy zakonczenia
			for (int i = 0; i < tasks; i++) {
				for (int j = 0; j < machines; j++) {
					endingTimes[i][j] = 0;
				}
			}
			// zwroc czas zakonczenia ostatniego zadania na ostatniej maszynie
			return getEndingTime(tasks - 1, machines - 1);
		}
		
		private void updateMakespanTime() {
			time = getMakespanTime();
		}
		
		private int getEndingTime(int task, int machine) {
			if (endingTimes[task][machine] != 0) // gdy juz jest obliczony
				return endingTimes[task][machine];
			else {
				int thisTaskOnPrevMachineET = 0;
				int prevTaskOnThisMachineET = 0;
				if (task != 0) // czy nie pierwsze zadanie
					prevTaskOnThisMachineET = getEndingTime(task - 1, machine);
				if (machine != 0) // czy nie pierwsza maszyna
					thisTaskOnPrevMachineET = getEndingTime(task, machine - 1);
				// dane zadanie zacznie sie wykonywac na danej maszynie gdy
				// - skonczy sie poprzednie na tej maszynie
				// - aktualne zakonczy sie na poprzedniej maszynie
				// czas zakonczenia pozniejszego z powyzszych jest czasem
				// rozpoczecia
				endingTimes[task][machine] = Math.max(prevTaskOnThisMachineET,
						thisTaskOnPrevMachineET) + _jobs[permutation[task]][machine];
				return endingTimes[task][machine];
			}
		
		}
		
		private void moveTowards(Firefly neighbour) {
			double  distance = 0.0; /* odleglosc (do czlonu beta_0 * exp(...) ) */
			double xi, xj; /* pomocnicze */
			/* wyznacz skladowe wektora polozenia */
			for (int i = 0; i < tasks; i++)
				for (int j = 0; j < tasks; j++) {
					/* metoda:
					 * 1 gdy i-te zadanie jest j-te w kolejnosci
					 * 0 w przeciwnym wypadku
					 */
					xi = permutation[j] == i ? 1 : 0;
					yi[i][j] = xi;
					/* to samo dla sasiada */
					xj = neighbour.permutation[j] == i ? 1 : 0;
					yj[i][j] = xj;
					/* dodaj do odleglosci */
					distance += Math.pow(xj - xi, 2);
				}
			/* metryka Euklidesowa */
			distance = Math.sqrt(distance);
			/* drugi czlon wzoru na nowe polozenie */
			double distanceFactor = beta0 * Math.exp(-gamma * Math.pow(distance, potega));
			/* zaktualizuj polozenie aktualnego swietlika */
			for (int i = 0; i < tasks; i++)
				for (int j = 0; j < tasks; j++)
					yi[i][j] += (yj[i][j] - yi[i][j]) * distanceFactor + alpha * (r.nextDouble() - 0.5);
			/* wyznacz prawdopodobienstwa
			 * Prawdopodobnie nie trzeba bo funkcja i tak jest
			 * rosnaca, ale jak chca to niech maja
			 */
			for (int i = 0; i < tasks; i++)
				for (int j = 0; j < tasks; j++)
					probabs[i][j] = 1.0 / (1.0 + Math.exp(-yi[i][j]));
			
			/* czas na wyznaczenie nowej permutacji
			 * Prawdopodobienstwo dotyczy "checi" objecia przez dane
			 * zadanie danego miejsca w permutacji, dlatego dajemy
			 * szanse najwiekszym prawdopodobienstwom. Kod
			 * wyjasnia o co chodzi dokladnie
			 */
			
			/* oznaczamy wszystkie pozycje w permutacji jako
			 * jeszcze nie uzyte
			 */
			for (int i = 0; i < tasks; i++)
				occupied[i] = false;
			/* pomocnicza anty-breakowa zmienna */
			boolean assigned;
			for (int i = 0; i < tasks; i++) {
				assigned = false; /* nic jeszcze sie nie stalo, wiec
									to jeszcze nie koniec */
				do { /* probuj znalezc najwyzszy mozliwy priorytet dla danego zadania */
					/* szukaj maksimum */
					int max = 0; /* to jest indeks, nie wartosc */
					for (int j = 1; j < tasks; j++)
						if (probabs[i][j] > probabs[i][max])
							max = j;
					if (occupied[max]) /* czy ktos juz zabral te pozycje permutacji */
						probabs[i][max] = -1.0; /* jesli tak, zmniejsz jej prawdopodobienstwo
										do poziomu ponizej niemozliwegp :) zeby nie mieszalo
						 				 i mozna bylo szukac kolejnych najwiekszych w kolejnej
						 				 iteracji */
					else { /* jupikaje! */
						permutation[max] = i; /* wloz do permutacji */
						occupied[max] = true; /* zablokuj innym */
						assigned = true; /* jedziemy do nastepnego zadania */
					}
				} while (!assigned);
			}

			/* jest nowa permutacja, wiec trza zaktualizowac
			 * wartosc funkcji celu (intensywnosc swiecenia)
			 */
			updateMakespanTime();
		}
		
		/* specjalny dodatek dla najlepszego, sprawdza
		 * poprzez zamiane sasiadujacych elementow czy moze
		 * nie udalo by sie dzieki temu poprawic sie jeszcze
		 */
		private void localSearch() {
			boolean swapped = false; /* znow anty-breakowa zmienna */
			for (int i = 0; i < tasks - 1 && !swapped; i++) {
				int temp; /* do zamiany */
				/* zamiana i-tego z (i+1)-wszym */
				temp = permutation[i];
				permutation[i] = permutation[i + 1];
				permutation[i + 1] = temp;
				/* czy jest lepiej? */
				int newTime = getMakespanTime();
				if (newTime < time) {
					time = newTime;
					swapped = true;
				}
				else { /* jesli nie ma poprawy, przywroc poprzednia */
					temp = permutation[i];
					permutation[i] = permutation[i + 1];
					permutation[i + 1] = temp;
				}
			}
		}
	}
	

	/* wyznacza najlepszego swietlika */
	public void findBest() {
		int bestTime = Integer.MAX_VALUE;
		for (int i = 0; i < ffs.length; i++) /* liniowe poszukiwanie */
			if (ffs[i].time < bestTime) {
				bestTime = ffs[i].time;
				best = i;
			}
		if (ffs[best].time < this.bestTime)
			this.bestTime = ffs[best].time;
	}
	

    @Override
    public boolean isCorrect(String parameter, String value) {
        return true;
    }
    
    @Override
    public void run(){
        for (int i = 0; i < 100; ++i){
    		/* porownaj kazdego z kazdym */
    		for (int j = 0; i < ffs.length; j++)
    			for (int k = 0; j < ffs.length; k++) {
    				/* time jest tak na prawde funkcja celu, a -time intensywnoscia */
    				if (ffs[j].time > ffs[k].time) { /* jsli jest jasniejszy */
    					ffs[j].moveTowards(ffs[k]); /* rusz dupsko */
    				}
    			}
    		/* wyznacz nowego najlepszego */
    		findBest();
    		/* i kaz mu sie sprobowac poprawic */
    		ffs[best].localSearch();
            this._result.newResult(ffs[best].permutation, bestTime);
        }
    }
}
